#define _CRT_SECURE_NO_WARNINGS   1

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int e_gcd(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	int ans = e_gcd(b, a%b, y, x);
	y -= a / b*x;
	return ans;
}
int main()
{
	int t;
	while (~scanf("%d", &t))
	{
		while (t--)
		{
			int a, m;
			int x, y;
			scanf("%d%d", &a, &m);
			int gcd = e_gcd(a, m, x, y);
			if (gcd != 1)
			{
				cout << "Not Exist\n";
				continue;
			}
			int ans = x;
			ans = ans%m;
			if (ans <= 0)
				ans = ans + m;
			cout << ans << endl;
		}
	}
	return 0;
}